1450E - Capitalism - CodeForces Solution

// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;

struct Edge {
	int start, end;
	int weight;
};

vector<int> dist(500, 0);
vector<Edge> edges(2500);

vector<int> color(500, -1);

vector<vector<int>> adj(200);
vector<vector<int>> d(200, vector<int>(200, (int) 1e9));

bool dfs(int node, int fill = 0) {
	if (color[node] != -1) {
		return color[node] == fill;
	}

	color[node] = fill;

	fill = (fill == 0 ? 1 : 0);

	for (int next : adj[node]) {
		if (!dfs(next, fill)) return false;
	}

	return true;
}

int main() {
	int N, M; cin >> N >> M;

	dist.resize(N);
	edges.resize(2 * M);
	color.resize(N);
	adj.resize(N);
	d.resize(N);

	for (int i = 0; i < N; i++) {
		d[i].resize(N);
		for (int j = 0; j < N; j++) {
			if (i == j) d[i][j] = 0;
			else d[i][j] = 1e9;
		}
	}

	for (int i = 0; i < M; i++) {
		int a, b, c; cin >> a >> b >> c; a--; b--;

		if (c == 0) {
			adj[a].push_back(b);
			adj[b].push_back(a);
			
			d[a][b] = 1;
			d[b][a] = 1;

			edges[2 * i].start = a; edges[2 * i].end = b; edges[2 * i].weight = 1;
			edges[2 * i + 1].start = b; edges[2 * i + 1].end = a; edges[2 * i + 1].weight = 1;
		} else {
			adj[a].push_back(b);
			adj[b].push_back(a);

			d[a][b] = 1;
			d[b][a] = -1;

			edges[2 * i].start = a; edges[2 * i].end = b; edges[2 * i].weight = 1;
			edges[2 * i + 1].start = b; edges[2 * i + 1].end = a; edges[2 * i + 1].weight = -1;
		}
	}

	// check for bipartite
	if (!dfs(0)) {
		cout << "NO" << endl;
		return 0;
	}

	// check for negative cycles
	for (int i = 0; i < N - 1; i++) {
		for (Edge edge : edges) {
			dist[edge.end] = min(dist[edge.end], dist[edge.start] + edge.weight);
		}
	}

	bool neg_cycle = false;
	
	for (Edge edge : edges) {
		if (dist[edge.end] > dist[edge.start] + edge.weight) neg_cycle = true;
	}

	if (neg_cycle) {
		cout << "NO" << endl;
		return 0;
	}

	// do floyd-warshall
	for (int k = 0; k < N; k++) {
    	for (int i = 0; i < N; i++) {
        	for (int j = 0; j < N; j++) {
            	d[i][j] = min(d[i][j], d[i][k] + d[k][j]); 
        	}
    	}
	}

	int maximum = -1; int max_row = -1;

	for (int i = 0; i < N; i++) {
		int tmp1 = -1;
		for (int j = 0; j < N; j++) {
			tmp1 = max(tmp1, d[i][j]);
		}

		if (tmp1 > maximum) {
			maximum = tmp1;
			max_row = i;
		}
	}

	cout << "YES" << endl;
	cout << maximum << endl;
	for (int i = 0; i < N; i++) {
		cout << d[max_row][i] << " ";
	}

	cout << endl;
}